from typing import List


def schedule_task(tasks: List[List[int]]):
    if len(tasks) == 0:
        return 0

    tasks = [x.copy() for x in tasks]
    for i in range(len(tasks)-1):
        for j in range(i+1, len(tasks)):
            a, b = tasks[i]
            c, d = tasks[j]
            cost1 = max(a+b, a+c+d)
            cost2 = max(c+d, c+a+b)
            if cost2 < cost1: #  or (cost2 == cost1 and b < d):
                temp = tasks[i]
                tasks[i] = tasks[j]
                tasks[j] = temp
    result = 0
    acc = 0
    for a, b in tasks:
        acc += a
        cur = acc + b
        result = max(result, cur)
    return result


def schedule_task2(tasks: List[List[int]]):
    if len(tasks) == 0:
        return 0
    tasks = [x.copy() for x in tasks]
    tasks = sorted(tasks, key=lambda x: x[1], reverse=True)
    result = 0
    acc = 0
    for a, b in tasks:
        acc += a
        cur = acc + b
        result = max(result, cur)
    return result


def brutal_solve(tasks):
    if len(tasks) == 0:
        return 0

    tasks = [x.copy() for x in tasks]
    from itertools import permutations

    result = 10 ** 10
    for ordered_tasks in permutations(tasks):
        acc = 0
        cur_result = 0
        for a, b in ordered_tasks:
            acc += a
            cur = acc + b
            cur_result = max(cur_result, cur)
        result = min(result, cur_result)
    # print(tasks)
    return result


def test():
    import random
    for i in range(1000):
        n = random.randint(0, 7)
        tasks = []
        for i in range(n):
            a = random.randint(1, 10)
            b = random.randint(1, 10)
            tasks.append([a, b])
        res1 = schedule_task2(tasks)
        res2 = brutal_solve(tasks)
        if res1 != res2:
            print(tasks, res1, res2)
test()
